\chapter{Variable Structure Models}
The composition of a variable structure model changes over time. New components are added as, for example, machinery is installed in a factory, organisms reproduce, or shells are fired from a cannon. Existing components are removed as machines break, organisms die, or shells in flight find their targets. Components are rearranged as, for example, parts move through a manufacturing process, organisms migrate, or a command and control network loses communication lines.

For modeling systems with a variable structure, \adevs\ provides a simple but effective mechanism to coordinate changes in structure and changes in state. This mechanism is based on the Dynamic DEVS modeling formalism described in A.M. Uhrmacher's paper ``Dynamic structures in modeling and simulation: a reflective approach", ACM Transactions on Modeling and Computer Simulation (TOMACS), Volume 11, Issue 2, pgs. 202-232, April 2001.

\section{Building and Simulating Variable Structure Models}
Every \classname{Network} and \classname{Atomic} model has a virtual method called \methodname{model\_transition}. This method is inherited from the \classname{Devs} class that is at the top of the \adevs\ class hierarchy. The signature of the \methodname{model\_transition} method is
\begin{verbatim}
bool model_transition()
\end{verbatim}
and its default implementation simply returns false.

At the end of every simulation cycle (that is, after computing the models' new states but prior to the garbage collection step) the simulator invokes the \methodname{model\_transition} method of every \classname{Atomic} model that changed state in that cycle. When the \methodname{model\_transition} method is invoked, the \classname{Atomic} model can do anything except alter the set of components of a \classname{Network} model.

If a model's \methodname{model\_transition} method returns true, then the simulator calls the \methodname{model\_transition} method of that model's parent. The parent is, of course, a \classname{Network} model, and its \methodname{model\_transition} method may add, remove, and rearrange the network's components. But it must not delete any components! The simulator will automatically delete components that are removed from the model when the structure change calculations are finished.

As before, if the \classname{Network}'s \methodname{model\_transition} method returns true then the simulator invokes the \methodname{model\_transition} method of its parent. Note, however, that the \methodname{model\_transition} method of any model is invoked at most once in each simulation cycle. This invocation, if it occurs, takes place after every component of the network qualifying for the evaluation of its \methodname{model\_transition} method has computed its change of structure.

After invoking every eligible model's \methodname{model\_transition} method, the simulator performs a somewhat complicated cleanup process. During this process the simulator constructs two sets. The first set contains 1) the components that belonged to all of the \classname{Network} models whose \methodname{model\_transition} method was invoked and 2) all of the components of every model in this set (i.e., this set is constructed recursively: if any model is in the set, so are its component models). The second set is defined in the same way, but it is computed using sets of components as they are after the \methodname{model\_transition} methods have been invoked.

The simulator deletes every model that has actually been removed. These are the models in the first set but not in the second. The simulator initializes every model that is genuinely new by computing its next event time (i.e., its creation time plus its time advance) and putting it into the event schedule. These are the models in the second second set but not in the first. The simulator leaves all other models alone.

The procedure for calculating a change of structure can be summarized as follows:
\begin{enumerate}
\item Calculate the \methodname{model\_transition} method of every atomic model that changed state.\label{var_struct_1}
\item Construct the set of network models that contain an atomic model from step \ref{var_struct_1} whose \methodname{model\_transition} method returned true. These network models are sort by their depth in the tree of models with the bottom-most first and top-most last. This ensures that structure changes are calculated from the bottom up. \label{var_struct_2}
\item Calculate the \methodname{model\_transition} methods of the networks in order. On completing each transition, do the following:
\begin{enumerate}
\item Remove the network from the list.
\item If the network's \methodname{model\_transition} method returns true, put the parent of the network into the sorted list of networks from step \ref{var_struct_2}. This ensures that a network's \methodname{model\_transition} method is invoked only after all of its eligible components have had their \methodname{model\_transition} method invoked.
\end{enumerate}
\item When there are no more networks in the list, do the following:
\begin{enumerate}
\item Delete the components removed from the model (i.e., the models without a parent).
\item Initialize the components that were added to the model.
\end{enumerate}
\end{enumerate}

The procedure for calculating a change of structure is illustrated in Fig. \ref{fig:set_defns}. The black models' \methodname{model\_transition} methods returned true. The set of components examined before and after the structure change are listed above the before (left) and after (right) trees. Notice that these models are in the sub-tree below the model $C$, which is the top-most model in that sub-tree that returned false from its \methodname{model\_transition} method. Also note that while the leaves of the tree may have had their model transition method invoked, none returns true and so their parents' model transition methods are not invoked nor are their sets of components considered when determining what models have been added and removed from the model. The set of deleted components is $\{c,D,d,e,f\}-\{e,g,d\} = \{c,D,f\}$. The set of new components is $\{e,g,d\} - \{c,D,d,e,f\} = \{g\}$.
\begin{figure}[ht]
\centering
\epsfig{file=var_struct_models_figs/var_struct_model_sets.eps}
\caption{Illustration of a change of structure in a variable structure model.}
\label{fig:set_defns}
\end{figure}

The \methodname{model\_transition} method can break the strict hierarchy and modularity that is usually observed when building \classname{Network} models. Any \classname{Network} model can, in principle, modify the set of components of any other model, regardless of proximity or hierarchy. The potential for anarchy is great, and so the design of a variable structure model should be considered carefully. There are two approaches to such a design that are simple and, in many cases, entirely adequate.

The first approach is to allow only \classname{Network} models to effect structure changes and to restrict those changes to the \classname{Network}'s immediate sub-components. With this approach, an \classname{Atomic} model initiates a structure change by posting a structure change request for its parent. The \classname{Atomic} model's \methodname{model\_transition} method returns true causing its parent's \methodname{model\_transition} method to be invoked. The parent \classname{Network} model then retrieves and acts on the requests posted by its components. The \classname{Network} repeats this process if it wants to effect structure changes involving models other than its immediate children; i.e., it posts a request for its parent and returns true from its \methodname{model\_transition} method.

The second approach allows arbitrary changes in structure by forcing the model at the top of the hierarchy to invoke its \methodname{model\_transition} method. This causes the simulator to consider every model in the aftermath of a structure change. As in the first approach, an \classname{Atomic} model that wants to effect a change of structure uses its \methodname{model\_transition} method to post a request for its parent. This request is percolated up the model hierarchy by the \classname{Network} models whose \methodname{model\_transition} methods always return true. 

The first approach trades flexibility for execution time. The second approach trades execution time for flexibility. With the first approach, structure changes that involve a small number of components require a small amount of work by the simulator. The scope of change must, however, be carefully restricted. With the second approach, every structure change requires the simulator to include every part of the model in its calculations, regardless of the actual extent of the change in structure. In this case, however, the scope of a structure change may be unlimited.

\section{A Variable Structure Example}
The Custom Widget Company is expanding its operations. Plans are being drawn for a new factory that will make custom gizmos (and to change the company name to The Custom Widget and Gizmo Company). The machines for the factory are expensive to operate. To keep costs down, the factory will operate just enough machinery to fill orders for gizmos. The factory must have enough machinery to meet peak demand, but much of the machinery will be idle much of the time. The factory engineers want answers to two questions: how many machines are needed and how much will it costs to operate them.

We will use a variable structure model to answer these questions. This model has three components: a generator that creates orders for gizmos, a model of a machine, and a model of the factory that contains the machines and that activates and deactivates machines as required to satisfy demand. The model of the factory is illustrated in Fig. \ref{fig:factory_model}.
\begin{figure}[ht]
\centering
\epsfig{file=var_struct_models_figs/factory_block_diagram.eps}
\caption{Block diagram of the model of the factory. The broken lines indicate structural elements that are subject to change.}
\label{fig:factory_model}
\end{figure}

The generator creates new orders for the factory. Each order is identified with an integer label, and the generator produces orders at the rate anticipated by the factory engineers. Demand at the factory is expected to be steady with a new order arriving every 1/2 to 2 days. This expected demand is modeled with a random variable that is uniformly distributed in [0.5,2]. Here is the code for the generator:
\begin{verbatim}
#include "adevs.h"
// The Genr models factory demand. It creates new orders every 0.5 to 2 days.
class Genr: public adevs::Atomic<int>
{
    public:
        /**
         * The generator requires a seed for the random number that determines
         * the time between new orders.
         */
        Genr(unsigned long seed):
           adevs::Atomic<int>(),next(1),u(seed){ set_time_to_order(); }
        // Internal transition updates the order counter and
		// determines the next arrival time
        void delta_int() { next++; set_time_to_order(); }
        // Output function produces the next order
        void output_func(adevs::Bag<int>& yb) { yb.insert(next); }
        // Time advance returns the time until the next order
        double ta() { return time_to_order; }
        // Model is input free, so these methods are empty
        void delta_ext(double,const adevs::Bag<int>&){}
        void delta_conf(const adevs::Bag<int>&){}
        // No explicit memory management is needed
        void gc_output(adevs::Bag<int>&){}
    private:
        // Next order ID
        int next;
        // Time until that order arrives
        double time_to_order;
        // Random variable for producing order arrival times
        adevs::rv u;
        // Method to set the order time
        void set_time_to_order() { time_to_order = u.uniform(0.5,2.0); }
};
\end{verbatim} 

The model of a machine is similar to the \classname{Clerk} in section \ref{chapter:intro}. A machine requires 3 days to make a gizmo, and orders for gizmos are processed first come, first serve. The \classname{Machine}'s \methodname{model\_transition} method is inherited from its \classname{Atomic} base class. I'll discuss the role of the \methodname{model\_transition} method after introducing the \classname{Factory} class. Here is the code for the \classname{Machine}.
\begin{verbatim}
#include "adevs.h"
#include <cassert>
#include <deque>
/**
 * This class models a machine as a fifo queue and server with fixed service time.
 * The model_transition method is used, in conjunction with the Factory model_transition
 * method, to add and remove machines as needed to satisfy a 6 day turnaround time
 * for orders. 
 */
class Machine: public adevs::Atomic<int> 
{
    public:
        Machine():adevs::Atomic<int>(),tleft(DBL_MAX){}
        void delta_int()
        {
            q.pop_front(); // Remove the completed job
            if (q.empty()) tleft = DBL_MAX; // Is the Machine idle?
            else tleft = 3.0; // Or is it still working?
        }
        void delta_ext(double e, const adevs::Bag<int>& xb)
        {
            // Update the remaining time if the machine is working
            if (!q.empty()) tleft -= e;
            // Put new orders into the queue
            adevs::Bag<int>::const_iterator iter = xb.begin();
            for (; iter != xb.end(); iter++) 
            {
                // If the machine is idle then set the service time
                if (q.empty()) tleft = 3.0;
                // Put the order into the back of the queue
                q.push_back(*iter);
            }
        }
        void delta_conf(const adevs::Bag<int>& xb)
        {
            delta_int();
            delta_ext(0.0,xb);
        }
        void output_func(adevs::Bag<int>& yb)
        {
            // Expel the completed order
            yb.insert(q.front());
        }
        double ta()
        {
            return tleft;
        }
        // The model transition function returns true if another order can not
        // be accommodated or if the machine is idle.
        bool model_transition()
        {
            // Check that the queue size is legal
            assert(q.size() <= 2);
            // Return the idle or full status
            return (q.size() == 0 || q.size() == 2);
        }
        // Get the number of orders in the queue
        unsigned int getQueueSize() const { return q.size(); }
        // No garbage collection 
        void gc_output(adevs::Bag<int>&){}
    private:
        // Queue for orders that are waiting to be processed
        std::deque<int> q;
        // Time remaining on the order at the front of the queue
        double tleft; 
};
\end{verbatim}

The number of \classname{Machine} models contained in the \classname{Factory} model at any time is determined by the current demand for gizmos. The real factory, of course, will have a fixed number of machines on the factory floor, but the planners do not know how many machines are needed. A variable structure model that creates and destroys machines as needed is a good way to accommodate this uncertainty. 

The Custom Widget and Gizmo Company has built its reputation on a guaranteed time of service, from order to delivery, of 15 days. This leaves only 6 days for the manufacturing process, the remaining time being consumed by order processing, delivery, etc. 

A single machine can meet this schedule if it has at most one order waiting in its queue at any time. However, it costs a dollar a day to operate a machine and so the factory engineers want to minimize the number of machines working at any time. To accomplish this goal, the factory's operating policy has two rules:
\begin{enumerate}
\item Assign incoming orders to the active machine that can provide the shortest turn around time and
\item keep just enough active machines to have capacity for one additional order.
\end{enumerate}

The \classname{Factory} model implements this policy in the following way. If a \classname{Machine} becomes idle or if its queue is full (i.e., the machine is working on one order and has another order waiting in its queue), then that machine's \methodname{model\_transition} method returns true. This causes the \classname{Factory}'s \methodname{model\_transition} method to be invoked. The \classname{Factory} first looks for and removes machines that have no work. Then it examines each remaining machine to determine if the required one unit of additional capacity is available. If the required unit of additional capacity is not available then the \classname{Factory} creates a new machine.

This is an example of the first approach to building a variable structure model. With this design, the simulator's structure calculations are done only when the \classname{Factory}'s \methodname{model\_transition} method is invoked, and these calculations are therefore limited to instants when \classname{Machine} models are likely to be created or destroyed. Our design, however, is complicated somewhat by the need for \classname{Machine} and \classname{Factory} objects to communicate; i.e., the \classname{Machine} models must watch their own status and inform the \classname{Factory} when there is a potential shortage of capacity.

If we had used the second approached to build our variable structure model, then the \classname{Machine}s' \methodname{model\_transition} method could have simply returned true: no need for a status check. The \classname{Factory} would iterate through its list of \classname{Machine}s, adding and deleting \classname{Machine}s as needed. This is more computationally expensive: the simulator looks for changes in the \classname{Factory}'s set of components at each simulation cycle. However, the design of the model is simpler, albeit only marginally so in this instance.

The \classname{Factory} is a \classname{Network} model and must implement all of the \classname{Network}'s virtual methods: \methodname{route}, \methodname{getComponents}, and \methodname{model\_transition}. The \methodname{route} method is responsible for assigning orders to machines. When an order arrives, it is sent to the machine that will most quickly satisfy the order. The \methodname{getComponents} method puts the current set of machines into the \classname{Set} c of components. The \methodname{model\_transition} method examines the status of each machine, deleting idle machines and adding new machines if they are needed to maintain reserve capacity. The \classname{Factory} implementation is shown below.
\begin{verbatim}
#include "adevs.h"
#include "Machine.h"
#include <list>

class Factory: public adevs::Network<int> {
   public:
      Factory();
      void getComponents(adevs::Set<adevs::Devs<int>*>& c);
      void route(const int& order, adevs::Devs<int>* src,
            adevs::Bag<adevs::Event<int> >& r);
      bool model_transition();
      ~Factory();
      // Get the number of machines
      int getMachineCount();
   private:
      // This is the machine set
      std::list<Machine*> machines;
      // Method for adding a machine to the factory
      void add_machine();
      // Compute time needed for a machine to finish a new job
      double compute_service_time(Machine* m);
};
\end{verbatim}
\begin{verbatim}
#include "Factory.h"
using namespace adevs;
using namespace std;

Factory::Factory():
Network<int>() { // call the parent constructor
   add_machine(); // Add the first machine the the machine set
}

void Factory::getComponents(Set<Devs<int>*>& c) {
   // Copy the machine set to c
   list<Machine*>::iterator iter;
   for (iter = machines.begin(); iter != machines.end(); iter++)
      c.insert(*iter);
}

void Factory::route(const int& order, Devs<int>* src, Bag<Event<int> >& r) {
   // If this is a machine output, then it leaves the factory
   if (src != this) { 
      r.insert(Event<int>(this,order));
      return;
   }
   // Otherwise, use the machine that can most quickly fill the order
   Machine* pick = NULL;  // No machine
   double pick_time = DBL_MAX; // Infinite time for service
   list<Machine*>::iterator iter;
   for (iter = machines.begin(); iter != machines.end(); iter++) {
      // If the machine is available
      if ((*iter)->getQueueSize() <= 1) {
         double candidate_time = compute_service_time(*iter);
         // If the candidate service time is smaller than the pick service time
         if (candidate_time < pick_time) {
            pick_time = candidate_time;
            pick = *iter;
         }
      }
   }
   // Make sure we found a machine with a small enough service time
   assert(pick != NULL && pick_time <= 6.0);
   // Use this machine to process the order
   r.insert(Event<int>(pick,order));
}

bool Factory::model_transition() {
   // Remove idle machines
   list<Machine*>::iterator iter = machines.begin();
   while (iter != machines.end()) {
      if ((*iter)->getQueueSize() == 0) iter = machines.erase(iter);
      else iter++;
   }
   // Add the new machine if we need it
   int spare_cap = 0;
   for (iter = machines.begin(); iter != machines.end(); iter++)
         spare_cap += 2 - (*iter)->getQueueSize();
   if (spare_cap == 0) add_machine();
   return false;
}

void Factory::add_machine() {
   machines.push_back(new Machine());
   machines.back()->setParent(this);
}

double Factory::compute_service_time(Machine* m) {
   // If the machine is already working
   if (m->ta() < DBL_MAX) return 3.0+(m->getQueueSize()-1)*3.0+m->ta();
   // Otherwise it is idle 
   else return 3.0;
}

int Factory::getMachineCount() {
   return machines.size();
}

Factory::~Factory() {
   // Delete all of the machines
   list<Machine*>::iterator iter;
   for (iter = machines.begin(); iter != machines.end(); iter++)
      delete *iter;
}
\end{verbatim}

To illustrate how the \methodname{model\_transition} method works, let us manually simulate the processing of a few orders. The first order arrives at day zero, the second order at day one, and the third order at day three. At the start, on day zero, there is one idle machine. When the first order arrives, the \classname{Factory}'s \methodname{route} method is invoked, and it sends the order to the idle machine. The \classname{Machine}'s \methodname{delta\_ext} method is invoked, and the machine begins processing the order. Next the \classname{Machine}'s \methodname{model\_transition} method is invoked. It discovers that the machine is working and has space in its queue, and so the \methodname{model\_transition} method returns false.

When the second order arrives on day one, the \classname{Factory}'s \methodname{route} method is called again. There is only one \classname{Machine} and it has space in its queue so the order is sent to that \classname{Machine}. The \classname{Machine}'s \methodname{delta\_ext} method is invoked and it queues the order. The \classname{Machine}'s \methodname{model\_transition} method is invoked next, and because the queue is full the method returns true. This causes the the \classname{Factory}'s \methodname{model\_transition} method to be invoked. It examines the \classname{Machine}'s status, sees that it is overloaded, and creates a new \classname{Machine}.

At this time, the working \classname{Machine} needs two more days to finish the first order, and it will not complete its second order until a total of five days have elapsed.

There is a great deal of activity when the third order arrives on day three. First, the working \classname{Machine}'s \methodname{output\_func} method is called, and it produces the first completed order (i.e., the order begun on day zero). Next the \classname{Factory}'s \methodname{route} method is called twice. The first call converts the \classname{Machine}'s output into an output from the \classname{Factory}. The second call routes the new order to the idle \classname{Machine}.

Now the state transition methods for the two \classname{Machine}s are invoked. The working \classname{Machine}'s \methodname{delta\_int} method is called and it starts work on its queued order. The idle \classname{Machine}'s \methodname{delta\_ext} method is called and it begins processing the new order. Lastly, the \methodname{model\_transition} methods of both \classname{Machine}s are invoked. Both \classname{Machine}'s have room in their queue and so both return false.

Suppose no orders arrive in the next three days. At day six, both machines finish their work. The \classname{Machine}s' \methodname{output\_func} methods are invoked, producing the finished orders. These become output from the \classname{Factory} via the \classname{Factory}'s \methodname{route} method.

Next, the \classname{Machine}s' \methodname{delta\_int} methods are called and both \classname{Machine}s become idle. After this, the \classname{Machine}s' \methodname{model\_transition} methods are invoked and these return true because the machines are idle. This causes the \classname{Factory}'s \methodname{model\_transition} method to be called. It examines each \classname{Machine}, sees that they are idle, and deletes both of them. Lastly the \classname{Factory} computes its available capacity, which is now zero, and creates a new machine. This returns the \classname{Factory} to its initial configuration with one idle \classname{Machine}.
 
The factory engineers have two questions: how many machines are needed and what is the factory's annual operating cost. These questions can be answered with a plot of the count of active machines versus time. The required number of machines is the maximum value of the active machine count. Each machine costs a dollar per day to operate, and so the operating cost is the one year time integral of the active machine count. A plot of the active machine count versus time is shown in Fig. \ref{fig:active_machine_plot}. The maximum count of active machines is four and the annual operating cost is \$944 (this plot is from the first simulation run listed in Table \ref{tab:monte_carlo_outcome}). 

\begin{figure}[ht]
\centering
\epsfig{file=var_struct_models_figs/machine_plot.eps}
\caption{Active machine count over one year.}
\label{fig:active_machine_plot}
\end{figure}
Because new orders arrive at random, the annual operating cost and maximum machine count are themselves random numbers. Consequently, data from several simulation runs are needed to make an informed decision. Table \ref{tab:monte_carlo_outcome} shows the outcomes of ten simulation runs. Each uses a different sequence of random numbers and therefore produces a different result (i.e., another sample of the maximum active machine count and annual operating cost). From this data, the factory engineers conclude that 4 machines are required and the average annual operating cost will be \$961.
\begin{table}[ht]
\centering
\begin{tabular}{|l|l|l|}
\hline
Random number seed & Maximum machine count & Annual operating cost \\ \hline
1 & 4 & \$944.05 \\ \hline
234 & 4 & \$968.58 \\ \hline
15667 & 4 & \$980.96 \\ \hline
999 & 3 & \$933.13 \\ \hline
9090133 & 4 & \$961.65 \\ \hline
6113 & 4 & \$977.33 \\ \hline
\end{tabular}
\caption{Outcomes of ten factory simulations.}
\label{tab:monte_carlo_outcome}
\end{table}

